package com.lw.leetcode.sort.c;

import java.util.Map;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 352. 将数据流变为多个不相交区间
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/9 17:45
 */
public class SummaryRanges {
    TreeMap<Integer, Integer> treeMap;

    public SummaryRanges() {
        treeMap = new TreeMap<>();
    }

    public void addNum(int val) {
        Integer l = treeMap.floorKey(val);
        if (l != null && l <= val && treeMap.get(l) >= val) {
            return;
        }
        Integer r = treeMap.ceilingKey(val);
        if (r != null && r == val) {
            return;
        }
        if (l == null || treeMap.get(l) < val - 1) {
            if (r == null || r > val + 1) {
                treeMap.put(val, val);
            } else {
                treeMap.put(val, treeMap.get(r));
                treeMap.remove(r);
            }
        } else {
            if (r == null || r > val + 1) {
                treeMap.put(l, val);
            } else {
                treeMap.put(l, treeMap.get(r));
                treeMap.remove(r);
            }
        }
    }

    public int[][] getIntervals() {
        int[][] ans = new int[treeMap.size()][2];
        int idx = 0;
        for (Map.Entry<Integer, Integer> entry : treeMap.entrySet()) {
            ans[idx][0] = entry.getKey();
            ans[idx++][1] = entry.getValue();
        }
        return ans;
    }

}
